import java.util.Stack;

public class Solution98 {
    /**
     * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
     * <p>
     * 假设一个二叉搜索树具有如下特征：
     * <p>
     * 节点的左子树只包含小于当前节点的数。
     * 节点的右子树只包含大于当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     * 示例 1:
     * <p>
     * 输入:
     * 2
     * / \
     * 1   3
     * 输出: true
     */
    // 递归
    public boolean isValidBST(TreeNode root) {
        return isValidBSCore(root, null, null);
    }

    public boolean isValidBSCore(TreeNode root, Integer lower, Integer upper) {
        if (root == null) {
            return true;
        }

        if (lower != null && root.val <= lower) {
            return false;
        }
        if (upper != null && root.val >= upper) {
            return false;
        }

        return isValidBSCore(root.left, lower, root.val) && isValidBSCore(root.right, root.val, upper);
    }

    // What F**K!!
    public boolean isValidBST2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        long inorder = Long.MIN_VALUE;
        //非递归版的中序遍历
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.val <= inorder) return false;
            inorder = root.val;
            root = root.right;
        }
        return true;
    }

    //递归版中序遍历
    long preVal = Long.MIN_VALUE;

    public boolean isValidBST3(TreeNode root){
        if (root == null){
            return true;
        }
        boolean left = isValidBST3(root.left);
        if (root.val <= preVal){
            return false;
        }
        preVal = root.val;
        boolean right = isValidBST3(root.right);
        return left && right;
    }
}
